#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣2616. 最小化数对的最大差值
// 【难度】中等
// 【提交】2025.9.23 https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/submissions/665280566/
// 【标签】二分查找；贪心算法
class Solution_LC2616 {
public:
    int minimizeMax(vector<int>& nums, int p) {
        if (p == 0) return 0;
        
        sort(nums.begin(), nums.end());
        
        auto check = [&](int mx) -> bool {
            int cnt = 0;
            for (int i = 0; i < nums.size() - 1; i++) {
                if (nums[i + 1] - nums[i] <= mx) {
                    cnt++;
                    i++;
                }
            }
            return cnt >= p;
        };
        
        int left = 0, right = nums.back() - nums[0];
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(mid)) {
                right = mid; 
            } else {
                left = mid + 1;
            }
        }
        return left;
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组nums和一个整数p，需要从数组中选择p个不重叠的数对（每个元素最多使用一次），
 * 使得所有数对差值的最大值最小化。
 * 模型：二分查找+贪心验证，通过二分法确定可能的最小最大差值。
 * 
 * 二、标准解法状态设计
 * 1. 对数组进行排序，便于计算相邻元素的差值。
 * 2. 使用二分查找确定可能的最小最大差值，范围是[0, 最大元素-最小元素]。
 * 3. 对于每个候选的最大差值mid，使用贪心算法验证是否能找到至少p个数对。
 * 
 * 三、你的实现思路
 * 使用二分查找法确定最小可能的最大差值，对于每个候选值使用贪心算法进行验证。
 * 贪心策略是尽可能选择相邻的差值小的数对，以最大化数对数量。
 * 
 * 四、逐行注释（带细节提醒）
 * if (p == 0) return 0; // 特殊情况处理
 * sort(nums.begin(), nums.end()); // 排序数组
 * 
 * auto check = [&](int mx) -> bool { // 定义检查函数
 *     int cnt = 0; // 计数器
 *     for (int i = 0; i < nums.size() - 1; i++) {
 *         if (nums[i + 1] - nums[i] <= mx) { // 如果差值不超过mx
 *             cnt++; // 增加数对计数
 *             i++; // 跳过下一个元素，避免重复使用
 *         }
 *     }
 *     return cnt >= p; // 返回是否找到足够数对
 * };
 * 
 * int left = 0, right = nums.back() - nums[0]; // 二分查找边界
 * while (left < right) { // 二分查找循环
 *     int mid = left + (right - left) / 2; // 计算中间值
 *     if (check(mid)) { // 如果mid可行
 *         right = mid; // 尝试更小的值
 *     } else {
 *         left = mid + 1; // 尝试更大的值
 *     }
 * }
 * return left; // 返回最小可行最大差值
 * 
 * 五、正确性证明
 * 排序后，相邻元素的差值最小，使用贪心策略优先选择相邻的差值小的数对是最优的。
 * 二分查找可以正确找到满足条件的最小最大差值，因为如果某个值mx可行，那么所有更大的值也可行。
 * 
 * 六、复杂度
 * 时间：O(n log n + n log M)，其中n是数组长度，M是最大可能的差值。
 *     排序需要O(n log n)，二分查找需要O(log M)次迭代，每次验证需要O(n)。
 * 空间：O(1)或O(log n)（排序的栈空间）。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 算法效率高，能够处理较大规模的数据；
 *   - 思路清晰，结合了二分查找和贪心算法的优点；
 *   - 代码实现简洁，易于理解。
 * 缺点：
 *   - 需要先排序，改变了原始数组的顺序；
 *   - 贪心策略的正确性需要一定的理解。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (nums.size() < 2 * p) return -1; // 如果元素不足
 * 2. 使用更明确的变量名（如 maxDiff 代替 mx）来增强可读性；
 * 3. 对于教学场景，可以添加注释解释为什么贪心策略是最优的；
 * 4. 可以考虑使用更高效的排序算法（如基数排序）如果输入范围有限。
 * 
 * 九、一句话总结
 * 通过二分查找确定最小可能的最大差值，并结合贪心算法进行验证，你的实现高效且准确，
 * 展现了解决最优化问题的经典方法。
 */